package classic;

/**
 * 题目：求一个整数的二进制表示中1的个数
 * 思路1：把该数字和1进行按位与操作，如果结果大于0说明最后一位为1，这样1的个数加1，然后循环把数字右移一位，
 * 继续进行上述操作，最终得到1的个数。这种解法有一个问题，如果为负数可能出现无限循环，故抛弃；
 * 思路2：在思路1的基础上，循环时不右移该数字，而是左移与它按位与的1，这样就不会出现负数时的问题
 * 思路3：思路2需要比较的次数为输入数字的二进制表示的长度（比如int型就是int型的位数），有没有更少比较次数的方法？考虑下面的情形：
 * a和(a-1)按位与的结果会消除最靠末位的一个1，那么循环对结果继续进行此操作，知道结果为0了，说明1
 * 消除完了，这种方法的比较次数就是数字包含1的个数，因此比思路2比较次数更少
 *
 * @author zj
 */
public class BitOneNum {
    public static void main(String[] args) {
        int number = -100;
        System.out.println(Integer.toBinaryString(number));
        System.out.println(bitOneCount(number));
        System.out.println(bitOneCount2(number));
    }

    public static int bitOneCount(int number) {
        int one = 1;
        int oneNum = 0;
        //循环的条件是one不为0，为0的话说明已经移出了int的位数了
        while (one != 0) {
            if ((one & number) > 0) {
                oneNum++;
            }
            one = one << 1;
        }
        if (number < 0) { //对于负数，还要加上一位符合
            oneNum++;
        }
        return oneNum;
    }

    public static int bitOneCount2(int number) {
        int oneNum = 0;
        int res = number;
        while (res != 0) {
            oneNum++;
            res = res & (res - 1);
        }
        return oneNum;
    }
}
